package editor.cn;

//统计所有小于非负整数 n 的质数的数量。 
//
// 
//
// 示例 1： 
//
// 输入：n = 10
//输出：4
//解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
// 
//
// 示例 2： 
//
// 输入：n = 0
//输出：0
// 
//
// 示例 3： 
//
// 输入：n = 1
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= n <= 5 * 106
// 
// Related Topics 哈希表 数学 
// 👍 620 👎 0

public class CountPrimes{
    public static void main(String[] args) {
        Solution solution = new CountPrimes().new Solution();
        System.out.println(solution.countPrimes(12));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        int count = 1;
        //从奇数开始就可以规避偶数
        for (int i = 3; i <n ; i+=2) {
            count += isPrime(i) ? 1 : 0;
        }
        return count;

    }

    boolean isPrime(int num) {
        //如16的因数8，16/8 也是16的因数，因此只需要效应到sqrt（16）
        int sqrt = (int) Math.sqrt(num);

        for (int i = 3; i<=sqrt; i+=2) {
            if ((num % i) == 0) {
                return false;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}